#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : MaximumGap.py
# @Time    : 2020/11/26 10:31
# @Description:
from typing import List


class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        """
        Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

        Return 0 if the array contains less than 2 elements.

        Example 1:
            Input: [3,6,9,1]
            Output: 3
            Explanation: The sorted form of the array is [1,3,6,9], either
                         (3,6) or (6,9) has the maximum difference 3.
        Example 2:
            Input: [10]
            Output: 0
            Explanation: The array contains less than 2 elements, therefore return 0.
        Note:
            - You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer
            range.
            - Try to solve it in linear time/space.

        :param nums:
        :return:
        """
        n = len(nums)
        if n < 2:
            return 0
        minVal = min(nums)
        maxVal = max(nums)

        max_gap = 0

        d = max(1, (maxVal - minVal) // (n - 1))
        bucket_size = (maxVal - minVal) // d + 1

        buckets = [[] for _ in range(bucket_size)]

        for i in range(n):
            lc = (nums[i] - minVal) // d
            buckets[lc].append(nums[i])

        prev_max = float('inf')
        for i in range(bucket_size):
            if buckets[i] and prev_max != float('inf'):
                max_gap = max(max_gap, min(buckets[i]) - prev_max)

            if buckets[i]:
                prev_max = max(buckets[i])

        # buckets = [[-1, -1] for _ in range(bucket_size)]
        # for i in range(n):
        #     lc = (nums[i] - minVal) // d
        #     if buckets[lc][0] == -1:
        #         buckets[lc][0] = buckets[lc][1] = nums[i]
        #     else:
        #         buckets[lc][0] = min(buckets[lc][0], nums[i])
        #         buckets[lc][1] = max(buckets[lc][1], nums[i])
        #
        # prev = -1
        # for i in range(bucket_size):
        #     if buckets[i][0] == -1:
        #         continue
        #     if prev != -1:
        #         max_gap = max(max_gap, buckets[i][0] - buckets[prev][1])
        #
        #     prev = i

        return max_gap


if __name__ == '__main__':
    S = Solution()
    nums = [1, 3, 4, 5, 6, 10, 11, 12, 17]
    # nums = [3, 6, 9, 1]
    print(S.maximumGap(nums))
    print('done')
